package com.peng.old.sort;

import com.peng.old.util.SortUtil;


/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = SortUtil.makeRandomArray(10000);
//        int[] arr = new int[]{1,2,6,2};//            2

//        long l = System.currentTimeMillis();
//        sort1(arr,0,arr.length-1);
//        System.out.println(System.currentTimeMillis()-l);
//        l = System.currentTimeMillis();
        sort2(arr,0,arr.length-1);
        System.out.println(SortUtil.checkResult(arr));
//        System.out.println(Arrays.toString(arr));
//        System.out.println(System.currentTimeMillis()-l);

    }


    public static void sort1(int[] arr, int left, int right) {
        if (left >= right) return;
        int i = divideAndConquer(arr, left, right);
        sort1(arr, left, i - 1);
//
        sort1(arr, i + 1, right);


    }

    public static void sort2(int[] arr, int left, int right) {
        if (left >= right) return;
        int i = divideAndConquer2(arr, left, right);
        sort2(arr, left, i - 1);
//
        sort2(arr, i + 1, right);


    }

    /**
     * 挖坑填坑式思路，
     * 从最开始的将第一个数作为基准值的坑挖出来，
     * 然后从右向左开始找有没有比基准值小的，
     * 如果有，将这个位置的数挖出来，填到这个第一个数的坑里，接着再从左侧开始找到一个比基准数大的数挖出来填到右侧刚刚被挖的坑中.....
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int divideAndConquer(int[] arr, int left, int right) {

        int i = left;

        int j = right;

        int x = arr[i];
        while (i < j) {
            while (i < j && arr[j] > x)
                j--;
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }

            while (i < j && arr[i] < x)
                i++;
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = x;

        return i;

    }

    /**
     *  取最右侧数作为基数，两边分别寻找到比基准值大的和比基准值小的数， 进行交换。  最后重合到一起的时候，将重合时的索引数与最右侧的基数值进行交换
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int divideAndConquer2(int[] arr, int left, int right) {

        int x = arr[right];

        int i = left;

        int j = right - 1;

        while (i <=j) {
            while (i <=j && arr[i] <= x)
                i++;
            while (i <=j && arr[j] > x)
                j--;
            if (i < j) {
                SortUtil.swap(arr, i, j);
            }
        }

            SortUtil.swap(arr, i, right);



        return i;


    }
}
